package h0906;

import java.util.ArrayList;
import java.util.List;

public class BracketGenerate {
    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }
    public static List<String> generateParenthesis(int n) {
        List<String> res=new ArrayList<>();
        backTrack(res,0,0,new StringBuilder(),n);
        return res;
    }

    //回溯
    private static void backTrack(List<String> res, int i, int j, StringBuilder temp,int n) {
        if (temp.length()==2*n){
            res.add(temp.toString());
        }
        if (i<n){
            temp.append("(");
            backTrack(res, i+1, j, temp, n);
            temp.setLength(temp.length()-1);
        }
        if (j<i){
            temp.append(")");
            backTrack(res, i, j+1, temp, n);
            temp.setLength(temp.length()-1);
        }
    }
}
